package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/11/20 10:37
 * @description： https://leetcode-cn.com/problems/longest-harmonious-subsequence/
 */
public class 最长和谐子序列 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.findLHS(new int[]{1, 1, 1, 1}));
    }


    /*// 排序-枚举
    class Solution {
        public int findLHS(int[] nums) {
            Arrays.sort(nums);
            int begin = 0;
            int max_len = 0;
            for (int end = 1; end < nums.length; end++) {
                while (nums[end] - nums[begin] > 1) begin++;
                if (nums[end] - nums[begin] == 1) {
                    max_len = Math.max(max_len, end - begin + 1);
                }
            }
            return max_len;
        }
    }*/

    class Solution {
        public int findLHS(int[] nums) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int num : nums) {
                map.put(num, map.getOrDefault(num, 0) + 1);
            }
            int max_len = 0;
            for (int num : map.keySet()) {
                if (map.containsKey(num + 1)) {
                    max_len = Math.max(max_len, map.get(num) + map.get(num + 1));
                }
            }
            return max_len;
        }
    }
}
